package lc_1373_二叉搜索子树的最大键值和;

public class Solution {

    /**
     * Definition for a binary tree node.
     ***/
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public int maxSumBST(TreeNode root) {
        return f(root)[4];
    }

    private int[] f(TreeNode root) {
        if (root == null) {
            return new int[] { 1, Integer.MAX_VALUE, Integer.MIN_VALUE, 0, 0 };
        }
        int v = root.val;
        int[] l = f(root.left);
        int[] r = f(root.right);
        if (l[0] == r[0] && r[0] == 1 && v > l[2] && v < r[1]) {
            int s = l[3] + r[3] + v;
            return new int[] { 1, Math.min(v, l[1]), Math.max(v, r[2]), s,
                    Math.max(s, Math.max(l[4], r[4])) };
        }
        return new int[] { 0, 0, 0, 0, Math.max(l[4], r[4]) };
    }
}